package com.lfg.leetcode.leetcode0;

public class No64minPathSum {

    public static void main(String[] args) {
        int[][] nums = new int[1][1];
        nums[0][0] = 1;
        int ret = minPathSum(nums);
        System.out.println(ret);
    }

    public static int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        for (int y = 1; y < m; y++) {
            grid[y][0] += grid[y-1][0];
        }
        for (int y = 1; y < n; y++) {
            grid[0][y] += grid[0][y-1];
        }
        for (int x = 1; x <m; x++) {
            for (int y = 1; y <n; y++) {
                grid[x][y] += Math.min(grid[x][y - 1], grid[x - 1][y]);
            }
        }
        return grid[m-1][n-1];
    }
}

